package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/5/22 22:38
 */
public class C1589 {

    public static int maxSumRangeQuery(int[] nums, int[][] requests) {
        int N = nums.length;
        Arrays.sort(nums);

        int[] indexMap = new int[N];
        for (int[] range : requests) {
            for (int i = range[0]; i <= range[1]; i++) {
                indexMap[i]++;
            }
        }
        // indexMap -> 下标:原下标   value: 代表查询的次数.
        Arrays.sort(indexMap);
        long ans = 0;
        for (int i = N-1; i >= 0; i--) {
            ans += nums[i] * indexMap[i];
        }
        return (int) (ans % 1000000007);
    }

    // 时间复杂度都是一样的, 这个利用优化了常数时间.
    public int maxSumRangeQuery2(int[] nums, int[][] requests) {
        int length = nums.length;
        int[] counts = new int[length];
        for (int[] request : requests) {
            int start = request[0], end = request[1];
            counts[start]++;
            if (end + 1 < length) {
                counts[end + 1]--;
            }
        }
        for (int i = 1; i < length; i++) {
            counts[i] += counts[i - 1];
        }
        Arrays.sort(counts);
        Arrays.sort(nums);
        long sum = 0;
        for (int i = length - 1; i >= 0 && counts[i] > 0; i--) {
            sum += (long) nums[i] * counts[i];
        }
        return (int) (sum % 1000000007);
    }

    // for test
    public static void main(String[] args) {

        System.out.println((long) (1000000000*1000000000));

        int[] nums = {1, 2, 3, 4, 5};
        int[][] requests = {{1, 3}, {0, 1}};
        System.out.println(maxSumRangeQuery(nums, requests));
    }

}
